{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #撞色搭配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sockCollocation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #撞色搭配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>整数数组 <code>sockets</code> 记录了一个袜子礼盒的颜色分布情况，其中 <code>sockets[i]</code> 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均有两只。请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sockets = [4, 5, 2, 4, 6, 6]\n",
    "<strong>输出：</strong>[2,5] 或 [5,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sockets = [1, 2, 4, 1, 4, 3, 12, 3]\n",
    "<strong>输出：</strong>[2,12] 或 [12,2]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= sockets.length &lt;= 10000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,5,2,4,6,6]', '[1,2,4,1,4,3,12,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        ret = 0\n",
    "        for n in sockets:\n",
    "            ret ^= n\n",
    "        div = 1\n",
    "        while (div & ret) == 0:\n",
    "            div = div << 1\n",
    "        a, b = 0, 0\n",
    "        for n in sockets:\n",
    "            if n & div:\n",
    "                a ^= n\n",
    "            else:\n",
    "                b ^= n\n",
    "        return a,b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        sockets.sort()\n",
    "        ans = []\n",
    "        for i in range(len(sockets)-1):\n",
    "            folllow = i + 1\n",
    "            if  sockets[i]^sockets[folllow]  == 0:\n",
    "                sockets[i] = 0\n",
    "                sockets[folllow] = 0\n",
    "        for i in sockets:\n",
    "            if i != 0:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        xor_res = 0\n",
    "        for i in sockets:\n",
    "            xor_res = xor_res ^ i \n",
    "        \n",
    "        last_1 = xor_res - (xor_res&(xor_res-1))\n",
    "        \n",
    "        xor_res1 = 0\n",
    "        xor_res2 = 0\n",
    "        for i in sockets:\n",
    "            if i&last_1:\n",
    "                xor_res1 = xor_res1 ^ i \n",
    "            else:\n",
    "                xor_res2 = xor_res2 ^ i\n",
    "        \n",
    "        return [xor_res1, xor_res2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x = 0\n",
    "        for s in sockets:\n",
    "            x ^= s\n",
    "\n",
    "        m = 1\n",
    "        while m & x == 0:\n",
    "            m <<= 1\n",
    "        x = y = 0\n",
    "        for s in sockets:\n",
    "            if s & m :\n",
    "                x ^= s\n",
    "            else:\n",
    "                y ^= s\n",
    "        return x,y\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        nums = sockets\n",
    "        re = 0\n",
    "        for x in nums:\n",
    "            re = re^x\n",
    "        ans = 1\n",
    "        re1,re2=0,0\n",
    "        while (re&ans)==0:\n",
    "            ans = (ans<<1)\n",
    "            \n",
    "        for x in nums:\n",
    "            if (x&ans):\n",
    "                re1 = (re1^x)\n",
    "            else:\n",
    "                re2 = (re2^x)\n",
    "        return [re1,re2]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        carry = 0\n",
    "        for s in sockets:\n",
    "            carry ^= s\n",
    "        for i in range(32):\n",
    "            if carry & (1<<i):\n",
    "                break\n",
    "        carry1, carry2 = 0, 0\n",
    "        for s in sockets:\n",
    "            if s & (1<<i):\n",
    "                carry1 ^= s\n",
    "            else:\n",
    "                carry2 ^= s\n",
    "        return [carry1, carry2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, n, m = 0, 0, 0, 1\n",
    "        for num in sockets:      # 1. 遍历异或\n",
    "            n ^= num\n",
    "        while n & m == 0:        # 2. 循环左移，计算 m\n",
    "            m <<= 1       \n",
    "        for num in sockets:      # 3. 遍历 sockets 分组\n",
    "            if num & m: x ^= num # 4. 当 num & m != 0\n",
    "            else: y ^= num       # 4. 当 num & m == 0\n",
    "        return x, y              # 5. 返回出现一次的数字\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x,y,n,m = 0,0,0,1\n",
    "        for socket in sockets:\n",
    "            n^=socket\n",
    "        while n&m ==0:\n",
    "            m<<=1\n",
    "        for socket in sockets:\n",
    "            if socket & m:x^=socket\n",
    "            else:y^=socket\n",
    "        return x ,y\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        res = [0, 0]\n",
    "        temp = 0\n",
    "        for i in sockets:\n",
    "            temp ^= i\n",
    "        k = 1\n",
    "        while k & temp == 0:\n",
    "            k <<= 1\n",
    "        for i in sockets:\n",
    "            if k & i == 0:\n",
    "                res[0] ^= i\n",
    "            else:\n",
    "                res[1] ^= i\n",
    "        res.sort(reverse=False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        ret = sockets[0]\n",
    "        for i in range(1, len(sockets)):\n",
    "            ret ^= sockets[i]\n",
    "        div = 1\n",
    "        while ret & div == 0:\n",
    "            div <<= 1\n",
    "        a, b = 0, 0\n",
    "        for i in range(len(sockets)):\n",
    "            if sockets[i] & div :\n",
    "                a ^= sockets[i]\n",
    "            else:\n",
    "                b ^= sockets[i]\n",
    "        return [a, b]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        xor = 0\n",
    "        for num in sockets:\n",
    "            xor ^= num\n",
    "        i = 0\n",
    "        while xor:\n",
    "            if xor % 2 == 1:\n",
    "                break\n",
    "            xor >>= 1\n",
    "            i += 1\n",
    "        a, b = 0, 0\n",
    "        for num in sockets:\n",
    "            if (num >> i) % 2 == 0:\n",
    "                a ^= num\n",
    "            else:\n",
    "                b ^= num\n",
    "        return [a, b]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, nums):\n",
    "        x, y, m, n = 0, 0, 1, 0\n",
    "        for num in nums:\n",
    "            n ^= num\n",
    "        while n & m == 0:\n",
    "            m <<= 1\n",
    "        for num in nums:\n",
    "            if num & m == 0:\n",
    "                x = x ^ num\n",
    "            else:\n",
    "                y = y ^ num\n",
    "        return x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        xor = 0\n",
    "        for s in sockets:\n",
    "            xor ^= s\n",
    "        \n",
    "        for i in range(32):\n",
    "            if (xor >> i) & 1:\n",
    "                break\n",
    "\n",
    "        res = [0, 0]\n",
    "        for n in sockets:\n",
    "            res[(n >> i) & 1] ^= n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, m, n = 0, 0, 0, 1\n",
    "        for num in sockets:\n",
    "            m ^= num\n",
    "        while m&n == 0:\n",
    "            n <<= 1\n",
    "        for num in sockets:\n",
    "            if num&n == 0:\n",
    "                x ^= num\n",
    "            else:\n",
    "                y ^= num\n",
    "        return x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        allXor = 0\n",
    "        for i in sockets:\n",
    "            allXor ^= i\n",
    "\n",
    "        factor = 1\n",
    "        while allXor & factor == 0:\n",
    "            factor <<= 1\n",
    "\n",
    "        x, y = 0, 0\n",
    "        for num in sockets:\n",
    "            if num & factor:\n",
    "                x ^= num\n",
    "            else:\n",
    "                y ^= num\n",
    "        return [x, y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, n, m = 0, 0, 0, 1\n",
    "        for num in sockets:      # 1. 遍历异或\n",
    "            n ^= num\n",
    "        while n & m == 0:        # 2. 循环左移，计算 m\n",
    "            m <<= 1       \n",
    "        for num in sockets:      # 3. 遍历 sockets 分组\n",
    "            if num & m: x ^= num # 4. 当 num & m != 0\n",
    "            else: y ^= num       # 4. 当 num & m == 0\n",
    "        return x, y              # 5. 返回出现一次的数字\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        xor = 0\n",
    "        for x in sockets:\n",
    "            xor ^= x\n",
    "        \n",
    "        last_one = xor & -xor\n",
    "        a,b = 0,0\n",
    "        for x in sockets:\n",
    "            if x & last_one:\n",
    "                a ^= x\n",
    "            else:\n",
    "                b ^= x\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        n = len(sockets)\n",
    "        check = 0\n",
    "        for i in range(n):\n",
    "            check ^= 1 << sockets[i]\n",
    "\n",
    "\n",
    "\n",
    "        tmp = check & -check\n",
    "        check -= tmp\n",
    "\n",
    "        return [int(log2(check)), int(log2(tmp))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        res = 0\n",
    "        for num in sockets:   # 假设要找的两个值为b.b\n",
    "            res ^= num    # 全员异或,相同的数字会抵消，剩下的值就是a^b的异或结果\n",
    "        div=1\n",
    "        while div & res == 0:\n",
    "            div = div << 1   # 只要res该位不是1，div就左移一位继续查找。1-->10-->100\n",
    "        m= n = 0\n",
    "        for num in sockets:\n",
    "            if num & div:\n",
    "                m ^= num\n",
    "            else:\n",
    "                n ^= num\n",
    "        return m,n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, nums: List[int]) -> List[int]:\n",
    "        res = 0\n",
    "        a = 0\n",
    "        b = 0\n",
    "        for num in nums:\n",
    "            res = num^res\n",
    "        h = 1\n",
    "        while res:\n",
    "            if res&h:\n",
    "                break\n",
    "            h<<=1\n",
    "        for num in nums:\n",
    "            if num&h:\n",
    "                a = a^num\n",
    "            else:\n",
    "                b = b^num\n",
    "        return [a,b]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, m, n = 0, 0, 1, 0\n",
    "        for num in sockets:\n",
    "            n ^= num\n",
    "        while m & n == 0:\n",
    "            m <<= 1\n",
    "        for num in sockets: \n",
    "            if num & m: x^=num\n",
    "            else:\n",
    "                y^=num\n",
    "        return [x, y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        mask = 0\n",
    "        for num in sockets:\n",
    "            mask = mask ^ num\n",
    "        \n",
    "        mask = mask & (-mask)\n",
    "\n",
    "        res = [0, 0]\n",
    "        for num in sockets:\n",
    "            if num & mask == 0:\n",
    "                res[0] ^= num\n",
    "            else:\n",
    "                res[1] ^= num\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, n, m = 0, 0, 0, 1\n",
    "        for num in sockets:         # 1. 遍历异或\n",
    "            n ^= num\n",
    "        while n & m == 0:        # 2. 循环左移，计算 m\n",
    "            m <<= 1       \n",
    "        for num in sockets:         # 3. 遍历 nums 分组\n",
    "            if num & m: x ^= num # 4. 当 num & m != 0\n",
    "            else: y ^= num       # 4. 当 num & m == 0\n",
    "        return x, y              # 5. 返回出现一次的数字\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, n, m = 0, 0, 0, 1\n",
    "        for num in sockets:\n",
    "            n ^= num\n",
    "        while n & m == 0:\n",
    "            m <<= 1 \n",
    "        for num in sockets:\n",
    "            if num & m:\n",
    "                x ^= num\n",
    "            else:\n",
    "                y ^= num\n",
    "        return x, y "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        res = 0\n",
    "        for _ in sockets:\n",
    "            res ^= _\n",
    "        \n",
    "        digit = 1\n",
    "\n",
    "        while (res & digit) == 0:\n",
    "            digit = digit << 1\n",
    "\n",
    "        partition_1, partition_2 = 0, 0\n",
    "\n",
    "        for sock in sockets:\n",
    "            if (sock & digit) != 0:\n",
    "                partition_1 ^= sock\n",
    "            else:\n",
    "                partition_2 ^= sock\n",
    "            \n",
    "        return [partition_1, partition_2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        mix = 0\n",
    "        for soc in sockets:\n",
    "            mix ^= soc\n",
    "        mask = 1\n",
    "        while mask & mix == 0:\n",
    "            mask <<= 1\n",
    "        # print(mask)\n",
    "        x, y = 0, 0\n",
    "        for soc in sockets:\n",
    "            if mask & soc == 0:\n",
    "                x ^= soc\n",
    "            else:\n",
    "                y ^= soc\n",
    "        return [x, y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        k = 0\n",
    "        for s in sockets:\n",
    "            k ^= s\n",
    "\n",
    "        div = 1\n",
    "        while k & div == 0:\n",
    "            div <<= 1\n",
    "\n",
    "        a, b = 0, 0\n",
    "        for s in sockets:\n",
    "            if s & div:\n",
    "                a ^= s\n",
    "            else:\n",
    "                b ^= s\n",
    "        return [a, b]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        tmp = 0 \n",
    "        for i in sockets:\n",
    "            tmp ^= i \n",
    "\n",
    "        index = 0\n",
    "        while tmp & 1 == 0:\n",
    "            index += 1 \n",
    "            tmp >>= 1 \n",
    "\n",
    "        res1, res2 = 0, 0 \n",
    "        for i in sockets:\n",
    "            if (i >> index) & 1:\n",
    "                res1 ^= i \n",
    "            else:\n",
    "                res2 ^= i \n",
    "        return [res1, res2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        n = len(sockets)\n",
    "        check = 0\n",
    "        for i in range(n):\n",
    "            check ^= 1 << sockets[i]\n",
    "\n",
    "        output = []\n",
    "        i = 0\n",
    "        while True:\n",
    "            if check & 1 << i:\n",
    "                output.append(i)\n",
    "                if len(output) == 2:\n",
    "                    break\n",
    "            i += 1\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        n,m,x,y = 0,1,0,0\n",
    "        for s in sockets:\n",
    "            n^= s\n",
    "        while n&m == 0 :\n",
    "            m<<=1\n",
    "        for s in sockets:\n",
    "            if s & m == 0:\n",
    "                x^= s\n",
    "            else: y^=s\n",
    "        return [x,y]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        ret = 0\n",
    "        for num in sockets:\n",
    "            ret = ret ^ num\n",
    "        div = 1\n",
    "        while (ret & div) == 0:\n",
    "            div = div << 1\n",
    "        a = 0\n",
    "        b = 0\n",
    "        for num in sockets:\n",
    "            if (num & div) == 0:\n",
    "                a ^= num\n",
    "            else:\n",
    "                b ^= num\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        xor_sum = functools.reduce(lambda x, y: x^y, sockets)\n",
    "        least_diff = 0\n",
    "        while 1 & (xor_sum >> least_diff) == 0:\n",
    "            least_diff += 1\n",
    "        \n",
    "        a, b = 0, 0\n",
    "        for socket in sockets:\n",
    "            if 1 & socket >> least_diff:\n",
    "                a ^= socket\n",
    "            else:\n",
    "                b ^= socket\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        ret = 0\n",
    "        for x in sockets:\n",
    "            ret ^= x\n",
    "        div = 1\n",
    "        while div & ret == 0:\n",
    "            div <<= 1\n",
    "        a, b = 0, 0\n",
    "        for x in sockets:\n",
    "            if x & div:\n",
    "                a ^= x\n",
    "            else:\n",
    "                b ^= x\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, n, m = 0, 0, 0, 1\n",
    "        for num in sockets:\n",
    "            n ^= num\n",
    "        while n & m == 0:\n",
    "            m <<= 1       \n",
    "        for num in sockets:\n",
    "            if num & m: x ^= num \n",
    "            else: y ^= num\n",
    "        return x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, n, m = 0, 0, 0, 1\n",
    "        for num in sockets:      # 1. 遍历异或\n",
    "            n ^= num\n",
    "        while n & m == 0:        # 2. 循环左移，计算 m\n",
    "            m <<= 1       \n",
    "        for num in sockets:      # 3. 遍历 sockets 分组\n",
    "            if num & m: x ^= num # 4. 当 num & m != 0\n",
    "            else: y ^= num       # 4. 当 num & m == 0\n",
    "        return x, y              # 5. 返回出现一次的数字\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        xor_sum = functools.reduce(lambda x, y: x^y, sockets)\n",
    "        \n",
    "        # least_diff = 0\n",
    "        # while 1 & (xor_sum >> least_diff) == 0:\n",
    "        #     least_diff += 1\n",
    "        \n",
    "        div = 1\n",
    "        while div & xor_sum == 0:\n",
    "            div <<= 1\n",
    "        \n",
    "        a, b = 0, 0\n",
    "        # for socket in sockets:\n",
    "        #     if 1 & socket >> least_diff:\n",
    "        #         a ^= socket\n",
    "        #     else:\n",
    "        #         b ^= socket\n",
    "        \n",
    "        for socket in sockets:\n",
    "            if socket & div:\n",
    "                a ^= socket\n",
    "            else:\n",
    "                b ^= socket\n",
    "        \n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        ret = functools.reduce(lambda x, y: x ^ y, sockets)\n",
    "        div = 1\n",
    "        while div & ret == 0:\n",
    "            div <<= 1\n",
    "        a, b = 0, 0\n",
    "        for socket in sockets:\n",
    "            if socket & div:\n",
    "                a ^= socket\n",
    "            else:\n",
    "                b ^= socket\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        ret = functools.reduce(lambda x, y: x ^ y, sockets)\n",
    "        div = 1\n",
    "        while div & ret == 0:\n",
    "            div <<= 1\n",
    "        a, b = 0, 0\n",
    "        for n in sockets:\n",
    "            if n & div:\n",
    "                a ^= n\n",
    "            else:\n",
    "                b ^= n\n",
    "        return [a, b]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        # 相同数字异或为0\n",
    "        # 将sockets拆为分别包含x和y的两个子数组\n",
    "        # x和y二进制至少有1位不同（分别为0和1）根据这位可以把socket拆分为分别包含x和y的两个子数组\n",
    "        temp = 0\n",
    "        for socket in sockets:\n",
    "            temp = temp ^ socket\n",
    "        \n",
    "        m = 1\n",
    "        while temp & m == 0:\n",
    "            m <<= 1\n",
    "        x, y = 0, 0\n",
    "        for socket in sockets:\n",
    "            if socket & m:\n",
    "                x ^= socket\n",
    "            else:\n",
    "                y ^= socket\n",
    "        return x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        k=[]\n",
    "        for i in sockets:\n",
    "            if i in k:\n",
    "                k.remove(i)\n",
    "            else:\n",
    "                k.append(i)\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        map = {}\n",
    "        for i in sockets:\n",
    "            if map.get(i, 0):\n",
    "                map[i] += 1\n",
    "            else:\n",
    "                map[i] = 1\n",
    "        out = []\n",
    "        for key,value in map.items():\n",
    "            if value==1:\n",
    "                out.append(key)\n",
    "        return out\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        res = 0\n",
    "        for item in sockets:\n",
    "            res ^= item\n",
    "        # 获取a和b的异或\n",
    "        \n",
    "        m = 1\n",
    "        while res & m == 0:\n",
    "            m <<= 1\n",
    "        \n",
    "        # 找到a和b不相同的一位\n",
    "\n",
    "        x,y = 0,0\n",
    "        # 利用找到的不同位，将数组分为两个部分，分别异或\n",
    "        for item in sockets:\n",
    "            if item&m == 0:\n",
    "                x^= item\n",
    "            else:\n",
    "                y^= item\n",
    "        return [x,y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        ret = functools.reduce(lambda x, y: x ^ y, sockets)\n",
    "        print(ret)\n",
    "        div = 1\n",
    "\n",
    "        while div & ret == 0:\n",
    "            div <<= 1\n",
    "        \n",
    "        a, b = 0, 0\n",
    "\n",
    "        for n in sockets:\n",
    "\n",
    "            if n & div:\n",
    "                a ^= n\n",
    "\n",
    "            else:\n",
    "                b ^= n\n",
    "        \n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        l = []\n",
    "        for i in sockets:\n",
    "            if sockets.count(i) == 1:\n",
    "                l.append(i)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        for s in sockets:\n",
    "            if s not in dic:\n",
    "                dic[s] = 1\n",
    "            else:\n",
    "                dic[s] += 1\n",
    "        a, b = 0, 0\n",
    "        _flag = True\n",
    "        for i, v in dic.items():\n",
    "            if v == 1:\n",
    "                if _flag:\n",
    "                    a = i\n",
    "                    _flag = False\n",
    "                else:\n",
    "                    b = i\n",
    "                    break\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        a,n = 0,len(sockets)\n",
    "        for i in range (0,n):\n",
    "            a^=sockets[i]\n",
    "        b,c = 0,0\n",
    "        mask = a & (-a)\n",
    "        for i in range(len(sockets)):\n",
    "            if(sockets[i] & mask == 0):\n",
    "                b^=sockets[i]\n",
    "            else:\n",
    "                c^=sockets[i]\n",
    "        return b,c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        color_map = 0\n",
    "        for s in sockets:\n",
    "            color_map ^= 1 << s\n",
    "        \n",
    "        pair = [0, 0]\n",
    "        count = 0\n",
    "        i = 0\n",
    "        mask = 1\n",
    "        while count < 2 and i < color_map.bit_length():\n",
    "            bit = color_map & mask\n",
    "            if bit != 0:\n",
    "                pair[count] = i\n",
    "                count += 1\n",
    "            mask <<= 1\n",
    "            i += 1\n",
    "        \n",
    "        return pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        d= dict()\n",
    "        for i in range(len(sockets)):\n",
    "            if sockets[i] in d:d[sockets[i]] = True\n",
    "            else:d[sockets[i]] = False\n",
    "        res = []\n",
    "        for n in d:\n",
    "            if not d[n]:res.append(n)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        \n",
    "        n,m = 0,1\n",
    "        x,y=0,0\n",
    "\n",
    "        for tem in sockets:\n",
    "            n ^= tem\n",
    "        \n",
    "        while n&m==0:\n",
    "            m = m<<1\n",
    "\n",
    "        for num in sockets:\n",
    "            if num&m: x^=num\n",
    "            else: y^=num\n",
    "        \n",
    "        return x,y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        ab = 0\n",
    "        for socket in sockets:\n",
    "            ab ^= socket\n",
    "        diff = ab & (-ab)\n",
    "        g1, g2 = 0, 0\n",
    "        for socket in sockets:\n",
    "            if socket & diff:\n",
    "                g1 ^= socket\n",
    "            else:\n",
    "                g2 ^= socket\n",
    "        return g1, g2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        hmap = {}\n",
    "        for i in sockets:\n",
    "            if i not in hmap:\n",
    "                hmap[i] = 1\n",
    "            else:\n",
    "                hmap[i] += 1\n",
    "        res = []\n",
    "        for j in hmap:\n",
    "            if hmap[j] == 1:\n",
    "                res.append(j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "\n",
    "        tmp = 0\n",
    "        for socket in sockets:\n",
    "            tmp ^= socket\n",
    "        div = 1\n",
    "        while tmp&div==0:\n",
    "            div <<= 1\n",
    "        a,b = 0,0\n",
    "        for socket in sockets:\n",
    "            if socket&div:\n",
    "                a ^= socket\n",
    "            else:\n",
    "                b ^= socket\n",
    "        return [a,b]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sockCollocation(self, sockets: List[int]) -> List[int]:\n",
    "        x, y, n, m = 0, 0, 0, 1\n",
    "        for num in sockets:\n",
    "            n ^= num\n",
    "        while n & m == 0:\n",
    "            m <<= 1\n",
    "        for num in sockets:\n",
    "            if num & m: x ^= num\n",
    "            else: y ^= num\n",
    "        return x, y"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
